Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations

摘要

In this paper we improve the layered implementation of arbitrary stabilizercircuits introduced by Aaronson and Gottesman in Phys. Rev. A 70(052328), 2004:to implement a general stabilizer circuit, we reduce their 11-stage computation-H-C-P-C-P-C-H-P-C-P-C- over the gate set consisting of Hadamard,Controlled-NOT, and Phase gates, into a 7-stage computation of the form-C-CZ-P-H-P-CZ-C-. We show arguments in support of using -CZ- stages over the-C- stages: not only the use of -CZ- stages allows a shorter layeredexpression, but -CZ- stages are simpler and appear to be easier to implementcompared to the -C- stages. Based on this decomposition, we develop a two-qubitgate depth-$(14n{-}4)$ implementation of stabilizer circuits over the gatelibrary {H, P, CNOT}, executable in the LNN architecture, improving bestpreviously known depth-$25n$ circuit, also executable in the LNN architecture.Our constructions rely on Bruhat decomposition of the symplectic group and onfolding arbitrarily long sequences of the form $($-P-C-$)^m$ into a 3-stagecomputation -P-CZ-C-. Our results include the reduction of the $11$-stagedecomposition -H-C-P-C-P-C-H-P-C-P-C- into a $9$-stage decomposition of theform -C-P-C-P-H-C-P-C-P-. This reduction is based on the Bruhat decompositionof the symplectic group. This result also implies a new normal form forstabilizer circuits. We show that a circuit in this normal form is optimal inthe number of Hadamard gates used. We also show that the normal form has anasymptotically optimal number of parameters.